import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by L.jp
 * Description:给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
 * User: 86189
 * Date: 2022-07-16
 * Time: 23:40
 */
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //bm算法
//        int voted = 1;
//        int res = array[0];
//        for(int i=1;i<array.length;i++){
//            if(array[i] == res){
//                voted++;
//            }else{
//                voted--;
//                if(voted == 0){
//                    voted = 1;
//                    res = array[i];
//                }
//            }
//        }
//        return res;
    
        //哈希表法
//        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //哈希表统计每个数字出现的次数
//        for(int i = 0; i < array.length; i++){ //遍历数组
//            if(!mp.containsKey(array[i]))
//                mp.put(array[i], 1);
//            else
//                mp.put(array[i], mp.get(array[i]) + 1);
//            if(mp.get(array[i]) > array.length / 2) //⼀旦有个数⼤于⻓度⼀半的情况即可返回
//                return array[i];
//        }
//        return 0;
    
        //统计法
        if(array == null || array.length==0) {
            return 0;
        }
        //法一：数组排序找到中位数之后再遍历数组找这个中位数，如果次数大于数组一半长度，那么就返回,这种方法比较简单，面试不推荐
        Arrays.sort(array);
        int mid= array[array.length/2];
        int count=0;//记录中位数出现的次数
        for(int num:array){
            if(num==mid){
                count++;
            }
        }
        if(count> array.length/2){
            return mid;
        }
        return 0;
        
    }

}
